/*
** Made by texane <texane@gmail.com>
** 
** Started on  Sun Jan  6 20:50:07 2008 texane
** Last update Wed Jan  9 00:33:11 2008 texane
*/



#include <stdio.h>
#include <stdlib.h>
#include "bst.h"



/* generate combination from 0 ... count
   insert them in a bst
   delete the elem 0
   delete the tree
 */



/* tree ops
 */

static void print_data(void* data, void* p)
{
  printf("%d ", (int)data);
}


static int cmp_data(void* data, void* ref)
{
  return (int)data - (int)ref;
}


static void nop(void* data, void* p)
{
  /* no operation, testing
   */
}


static void count_node(void* data, void* count)
{
  ++*(unsigned int*)count;
}


/* create a tree
 */

static bst_tree_t* create_bst_tree(int* values,
				   unsigned int count)
{
  unsigned int i;
  bst_node_t* node;
  bst_tree_t* tree;

  tree = malloc(sizeof(bst_tree_t));
  if (tree == NULL)
    return NULL;

  bst_tree_init(tree);

  for (i = 0; i < count; ++i)
    {
      node = malloc(sizeof(bst_node_t));
      if (node != NULL)
	{
	  bst_node_init(node);
	  node->data = (void*)values[i];
	  bst_tree_insert_node(tree, node, cmp_data);
	  bst_tree_foreach_node(tree, nop, NULL);
	}
    }

  return tree;
}



/* delete a tree
 */

static void delete_node(bst_node_t* node)
{
  free(node);
}

static void delete_bst_tree(bst_tree_t* tree)
{
  bst_tree_release(tree, delete_node);
  free(tree);
}



/* tree print
 */

static void print_bst_tree(bst_tree_t* tree)
{
  bst_tree_foreach_node(tree, print_data, NULL);
  printf("\n");
}


/* tree count
 */

static unsigned int count_bst_tree(bst_tree_t* tree)
{
  unsigned int count;

  count = 0;
  bst_tree_foreach_node(tree, count_node, &count);

  return count;
}


/* invalid a node
 */

static void invalid_node(bst_node_t* node)
{
  node->next = (bst_node_t*)42;
  node->prev = (bst_node_t*)42;
  node->parent = (bst_node_t*)42;
  node->right = (bst_node_t*)42;
  node->left = (bst_node_t*)42;
}



/* generate all perms
 */

#if 0
# define DEBUG_STEP() printf("[?]: %d\n", __LINE__)
#else
# define DEBUG_STEP()
#endif

#define VALUE_SIZE 7

static void print_values(const int* values,
			 unsigned int count)
{
  unsigned int i;
  unsigned int j;
  char buf[64];

  j = 0;
  for (i = 0; i < count; ++i)
    j += sprintf(buf + j, " %d", values[i]);
  buf[j] = 0;
  printf("%s\r", buf);
}


static void gen_perms_rec(int* values,
			  unsigned int pos,
			  unsigned int value_count)
{
  int value;
  unsigned int count;
  bst_tree_t* tree;
  bst_node_t* node;

  if (pos == value_count)
    {
      DEBUG_STEP();

      tree = create_bst_tree(values, pos);

      DEBUG_STEP();

      if (tree != NULL)
	{
	  DEBUG_STEP();

	  count = 0;

	  /* test deletion
	   */
	  while (bst_tree_find_node(tree, cmp_data, (void*)0, &node) != -1)
	    {
	      DEBUG_STEP();
	      bst_tree_remove_node(tree, node);
	      DEBUG_STEP();
	      bst_tree_foreach_node(tree, nop, NULL);
	      DEBUG_STEP();
	      invalid_node(node);
	      free(node);
	      ++count;
	    }

	  DEBUG_STEP();

	  /* test list walking
	   */
	  if (count_bst_tree(tree) != (pos - count))
	    {
	      printf("\n[!] count_bst_tree(%d) != (pos(%d) - count(%d))(%d)\n",
		     count_bst_tree(tree),
		     pos,
		     count,
		     pos - count);
	      print_bst_tree(tree);
	      exit(-1);
	    }

	  DEBUG_STEP();

	  /* test insertion after deletion
	   */
	  while (count--)
	    {
	      DEBUG_STEP();

	      node = malloc(sizeof(bst_node_t));
	      if (node != NULL)
		{
		  bst_node_init(node);
		  node->data = (void*)0;
		  bst_tree_insert_node(tree, node, cmp_data);
		}
	    }

	  DEBUG_STEP();

	  if (count_bst_tree(tree) != pos)
	    {
	      printf("[!] count_bst_tree != pos - count\n");
	      exit(-1);
	    }

	  DEBUG_STEP();

	  delete_bst_tree(tree);

	  DEBUG_STEP();
	}
      else
	{
	  perror("malloc");
	  exit(-1);
	}

      DEBUG_STEP();
    }
  else
    {
      for (value = 0; value < value_count; ++value)
	{
	  values[pos] = value;
	  print_values(values, value_count);
	  gen_perms_rec(values, pos + 1, value_count);
	}
    }
}


static void gen_perms(int ac, const char** av)
{
  int values[VALUE_SIZE] = { 0, };
  unsigned int pos;

  for (pos = 0; av[pos] != NULL; ++pos)
    values[pos] = atoi(av[pos]);

  gen_perms_rec(values, pos, VALUE_SIZE);

  printf("\n");
}


int main(int ac, char** av)
{
  gen_perms(ac - 1, (const char**)(av + 1));

  return 0;
}
